#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void Swap(int* s1, int* s2)
{
	int temp = *s1;
	*s1 = *s2;
	*s2 = temp;
}

///////////////////////////////////////////////////////////////////////////////////
// 冒泡排序
// 时间复杂度 O(n2)
// 空间复杂度 O(1)
// 稳定排序
void BubbleSort(int arr[], int size)
{
	if(size <= 1) {
		return;
	}

	// bound 代表当前已有序的元素个数
	int bound = 0;
	for( ; bound < size; ++bound) {
		// 本次循环找到一个最小的数字
		int cur = size - 1;
		for( ; cur > bound; --cur) {
			if(arr[cur] < arr[cur - 1]) {
				Swap(&arr[cur], &arr[cur - 1]);
			} // end if
		} // end for
	} // end for
	return;
}

///////////////////////////////////////////////////////////////////////////////////
// 选择排序(打擂台)
// 时间复杂度 O(n2)
// 空间复杂度 O(1)
// 不稳定
void SelectSort(int arr[], int size)
{
	if(NULL == arr || size <= 1) {
		return;
	}
	int bound = 0;
	for( ; bound < size; ++bound) {
		int cur = bound;
		for( ; cur < size; ++cur) {
			if(arr[cur] < arr[bound]) {
				Swap(&arr[cur], &arr[bound]);
			} // end if
		} // end for
	} // end for
	return;
}

///////////////////////////////////////////////////////////////////////////////////
// 插入排序
// 时间复杂度 O(n2)
// 空间复杂度 O(1)
// 稳定排序
void InsertSort(int arr[], int size)
{
	if(NULL == arr || size <= 1) {
		return;
	}

	int bound = 1;
	for( ; bound < size; ++bound) {
		int temp = arr[bound];
		int cur = bound;
		for( ; cur > 0; --cur) {
			if(arr[cur - 1] > temp) {
				arr[cur] = arr[cur - 1];
			} else {
				break;
			}
		}
		// 如果temp是当前序列中最小的元素，那么就会走到cur为0的位置
		// 此时将最小的元素放到最低位
		//
		// 如果已经是有序序列，则放回原位
		arr[cur] = temp;
	}
}

///////////////////////////////////////////////////////////////////////////////////
// 堆排序
// 非递归时间复杂度为 O(nlogn)
// 空间复杂度为 O(1)
void AdjustDown(int arr[], int size, int parent)
{
	while(parent < size) {
		int left = parent * 2 + 1;
		int right = parent * 2 + 2;

		if(left > size) {
			return;
		}

		int maxChild = left;

		if((right < size) && (arr[right] > arr[left])) {
			maxChild = right;
		}

		if(arr[parent] < arr[maxChild]) {
			return;
		}

		Swap(&arr[parent], &arr[maxChild]);

		parent = maxChild;
	}

//	int left = parent * 2 + 1;
//	int right = parent * 2 + 2;
//
//	// 判断是不是叶子结点
//	if(left >= size) {
//		// 如果是叶子结点就返回
//		return;
//	}
//
//	int maxChild = left;
//	if(right < size || arr[right] > arr[left]) {
//		maxChild = right;
//	}
//
//	if(arr[maxChild] > arr[parent]) {
//		// 如果满足堆条件就返回
//		return;
//	}
//	Swap(&arr[maxChild], &arr[parent]);
//
//	AdjustDown(arr, size, maxChild);
}

void HeapSort(int arr[], int size)
{
	if(NULL == arr || size <= 1) {
		return;
	}

	int parent = size/2 - 1;
	for( ; parent > 0; --parent) {
		AdjustDown(arr, size, parent);
	}
	return;
}

///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
// 快速排序
// 最差情况下时间复杂度为 O(n2)
// 平均情况时间复杂度为 O(1)
// 空间复杂度为 O(n)
// 非稳定排序
void QuickSort(int arr[], int size);

void SortPri(int arr[], int size)
{
	if(size <= 1 || arr == NULL) {
		return;
	}

	int i = 0;
	for( ; i < size; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void TestSort()
{
	int arr[] = {7, 2, 0, 1, 9, 8, 4, 3, 5};
	int size = sizeof(arr)/sizeof(int);

	BubbleSort(arr, size);
	SortPri(arr, size);

	SelectSort(arr, size);
	SortPri(arr, size);

	InsertSort(arr, size);
	SortPri(arr, size);

	HeapSort(arr, size);
	SortPri(arr, size);
}

int main()
{
	TestSort();
	return 0;
}
